Paper 2013/879

Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture

Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza

Abstract

We build a system that provides succinct non-interactive zero-knowledge proofs (zk-SNARKs) for program executions on a von Neumann RISC architecture. The system has two components: a cryptographic proof system for verifying satisfiability of arithmetic circuits, and a circuit generator to translate program executions to such circuits. Our design of both components improves in functionality and efficiency over prior work, as follows. Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. Moreover, the size of the output circuit depends additively (rather than multiplicatively) on program size, allowing verification of larger programs. The cryptographic proof system improves proving and verification times, by leveraging new algorithms and a pairing library tailored to the protocol. We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and also demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 milliseconds, regardless of the original program's running time.

Note: The updated version fixes an error in Appendix B, found by Ariel Gabizon.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2014
Keywords
zero-knowledgesuccinct argumentscomputationally-sound proofs
Contact author(s)
alexch @ csail mit edu
History
2019-02-05: last of 8 revisions
2013-12-30: received
See all versions
Short URL
https://ia.cr/2013/879
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/879,
      author = {Eli Ben-Sasson and Alessandro Chiesa and Eran Tromer and Madars Virza},
      title = {Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/879},
      year = {2013},
      url = {https://eprint.iacr.org/2013/879}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.